#include<iostream>
#include<malloc.h>
using namespace std;
#define arrlen 50

//子数组归并
void merge(int arr[], int start, int mid, int end)
{
	int result[arrlen];//创建一个新数组用来存放待排序的子数组
	int k = 0;			//临时数组的下标
	int i = start, j = mid+1;
	while (i <=mid && j <=end)//两个子数组作比较，数值小的先放进临时数组，大的后放
	{
		if (arr[i] < arr[j])
		{
			result[k] = arr[i];
			k++;
			i++;
		}
		else
		{
			result[k] = arr[j];
			k++;
			j++;
		}
	}
		if (i == mid + 1)//将右半区的为排序元素直接放到后面
		{
			while (j <= end)
			{
				result[k++] = arr[j++];
			}
			
		}
		if (j == end + 1)//将左半区的为排序元素直接放到后面
			{
				while (i <= mid)
				{
					result[k++] = arr[i++];
				}
			}
		for (int j = 0, i = start; j < k; i++, j++)//将排好序的数组复制到原数组中
		{
			arr[i] = result[j];
		}
}

//数组拆分，归并入口
void mergesort(int arr[], int start, int end)
{
	if (start == end)
	{
		return;
	}
	else
	{
		int mid = (start + end) / 2;//取中间值
		mergesort(arr, start, mid);//将数组拆分成若干个子数组
		mergesort(arr, mid + 1, end);
		merge(arr, start, mid, end);
	}
}
int main()
{
	int arr[10] = { 13,6,12,9,5,31,3,24,5,1 };
	mergesort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}
